import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-26
 * Time: 22:08
 */
public class Solution {
    public static int openLock(String[] deadEnds, String target) {
        // 开始 == 结束, 直接返回 0
        if(target.equals("0000")){
            return 0;
        }
        Set<String> dead = new HashSet<>(Arrays.asList(deadEnds));
        // 目标是死亡数字
        // 根本不能到达目标位置
        if(dead.contains("0000")){
            return -1;
        }
        Set<String> visited = new HashSet<>();
        visited.add("0000");
        Queue<String> queue = new LinkedList<>();
        queue.add("0000");
        int count = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String num = queue.poll();
                for (int j = 0; j < num.length(); j++) {
                    // 因为转盘的每个数字可以朝着两个方向转
                    char[] arr = num.toCharArray();
                    // 先试着向数字大的方向拨
                    if(arr[j] == '9'){
                        arr[j] = '0';
                    }else{
                        arr[j]++;
                    }
                    String newNum = String.valueOf(arr);
                    if(newNum.equals(target)){
                        return count;
                    }
                    if(!dead.contains(newNum) && !visited.contains(newNum)){
                        queue.add(newNum);
                        visited.add(newNum);
                    }
                    // 再试往数字小的方向拨
                    arr = num.toCharArray();
                    if(arr[j] == '0'){
                        arr[j] = '9';
                    }else{
                        arr[j]--;
                    }
                    String newNum2 = String.valueOf(arr);
                    if(newNum2.equals(target)){
                        return count;
                    }
                    if(!dead.contains(newNum2) && !visited.contains(newNum2)){
                        queue.add(newNum2);
                        visited.add(newNum2);
                    }
                }
            }
            count++;
        }
        return -1;
    }
}